package com.itheima.datastructure.linkedlist;

import java.util.Iterator;
import java.util.function.Consumer;

/**
 * 单向链表(带哨兵) - 泛型版本
 */
public class SinglyLinkedListSentinel01<E> implements Iterable<E> { // 整体
    private Node head = new Node(null, null); // 头指针(哨兵节点)

    @Override
    public Iterator<E> iterator() {


        return new Iterator<E>() {
            Node p = head.next;

            @Override
            public boolean hasNext() { // 判断是否还有下一个元素
                return p != null;
            }

            @Override
            public E next() {
                E v = (E) p.value;// 返回当前值
                p = p.next; //并指向下一个元素
                return v;
            }
        };
    }


    /**
     * 节点类
     */
    private static class Node<E> {
        E value; // 值
        Node<E> next; // 下一个节点指针

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 向链表头部添加
     *
     * @param value 待添加值
     */
    public void addFirst(E value) {
        insert(0, value);
    }

    /**
     * 遍历链表1
     *
     * @param consumer 要执行的操作
     */
    public void loop1(Consumer<E> consumer) {
        Node<E> p = head.next;
        while (p != null) {
            consumer.accept(p.value);
            p = p.next;
        }
    }

    /**
     * 遍历链表2
     *
     * @param consumer 要执行的操作
     */
    public void loop2(Consumer<E> consumer) {
        for (Node<E> p = head.next; p != null; p = p.next) {
            consumer.accept(p.value);
        }
    }

    public void loop3(Consumer<E> consumer) {
        recursiveLoop(head.next, consumer);
    }

    private void recursiveLoop(Node<E> p, Consumer<E> consumer) {
        if (p == null) {
            return;
        }
        consumer.accept(p.value);
        recursiveLoop(p.next, consumer);
    }

    private Node<E> findLast() {
//        Node<E> p;
//        for (p = head; p.next != null; p = p.next) {
//
//        }
//        return p;

        // 使用while循环
        Node p = head;
        while (p.next != null) {
            p = p.next;
        }
        return p;

    }

    /**
     * 向链表尾部添加
     *
     * @param value 待添加值
     */
    public void addLast(E value) {
        Node<E> last = findLast();
        last.next = new Node<>(value, null);
    }


    // 索引查找
    private Node<E> findNode(int index) {
        checkIndex(index);
//        int i = -1;
//        for (Node<E> p = head; p != null; p = p.next, i++) {
//            if (i == index) {
//                return p;
//            }
//        }
//        return null; // 没找到

        // --- 使用while ---
        int idx = -1;
        Node<E> p = head;
        while (p != null) {
            if (idx == index) {
                return p;
            }
            p = p.next;
            idx++;
        }
        return null; // 没找到
    }

    /**
     * 根据索引查找
     *
     * @param index 索引
     * @return 找到, 返回该索引位置节点的值
     * @throws IllegalArgumentException 找不到, 抛出 index 非法异常
     */
    public E get(int index) throws IllegalArgumentException {
        checkIndex(index);
        Node<E> node = findNode(index);
        if (node == null) {
            throw illegalIndex(index);
        }
        return node.value;
    }

    private void checkIndex(int index) {
        if (index < 0) {
            throw illegalIndex(index);
        }
    }

    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index [%d] 不合法%n", index));
    }

    /**
     * 向索引位置插入
     *
     * @param index 索引
     * @param value 待插入值
     * @throws IllegalArgumentException 找不到, 抛出 index 非法异常
     */
    public void insert(int index, E value) throws IllegalArgumentException {
        // 找到上一个节点
        Node<E> prev = findNode(index - 1);
        if (prev == null) { // 找不到
            throw illegalIndex(index);
        }
        //将新节点插入 prev 和 next 之间
//        Node<E> next = prev.next;
//        Node crr = new Node<>(value, next);
//        prev.next = crr;

        prev.next = new Node<>(value, prev.next);
    }

    /**
     * 删除第一个
     *
     * @throws IllegalArgumentException - 如果不存在, 抛出 index 非法异常
     */
    public void removeFirst() throws IllegalArgumentException {
        remove(0);
    }

    /**
     * 从索引位置删除
     *
     * @param index 索引
     * @throws IllegalArgumentException 找不到, 抛出 index 非法异常
     */
    public void remove(int index) throws IllegalArgumentException {
        Node<E> prev = findNode(index - 1); // 上一个节点
        if (prev == null) {
            throw illegalIndex(index);
        }
        Node<E> removed = prev.next; // 被删除的节点
        if (removed == null) {
            throw illegalIndex(index);
        }
        prev.next = removed.next;
    }
}
